home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / SC_TTT.ZIP / sc_ttt.c next >
C/C++ Source or Header  |  1995-04-14  |  7KB  |  274 lines
  1. /* Tic-Tac-Toe program by Steve Chapel schapel@cs.ucsb.edu
  2.    Uses alpha-beta pruning minimax search to play a "perfect" game.
  3.    The alpha-beta pruning can be removed, but will increase search time.
  4.    The heuristic and move ordering in Best_Move() can also be removed with
  5.      an increase in search time. */
  6.  
  7. #include <stdio.h>
  8. #include <ctype.h>
  9.  
  10. #define String_Length 80
  11.  
  12. #define Squares 9
  13. typedef char Square_Type;
  14. typedef Square_Type Board_Type[Squares];
  15. const Square_Type Empty = ' ';
  16.  
  17. const int Infinity = 10;        /* Higher value than any score */
  18. const int Maximum_Moves = Squares;    /* Maximum moves in a game */
  19.  
  20. int Total_Nodes;            /* Nodes searched with minimax */
  21.  
  22. /* Array describing the eight combinations of three squares in a row */
  23. #define Possible_Wins 8
  24. const int Three_in_a_Row[Possible_Wins][3] = {
  25.     { 0, 1, 2 },
  26.     { 3, 4, 5 },
  27.     { 6, 7, 8 },
  28.     { 0, 3, 6 },
  29.     { 1, 4, 7 },
  30.     { 2, 5, 8 },
  31.     { 0, 4, 8 },
  32.     { 2, 4, 6 }
  33. };
  34.  
  35. /* Array used in heuristic formula for each move. */
  36. const int Heuristic_Array[4][4] = {
  37.     {     0,   -10,  -100, -1000 },
  38.     {    10,     0,     0,     0 },
  39.     {   100,     0,     0,     0 },
  40.     {  1000,     0,     0,     0 }
  41. };
  42.  
  43. /* Structure to hold a move and its heuristic */
  44. typedef struct {
  45.     int Square;
  46.     int Heuristic;
  47. } Move_Heuristic_Type;
  48.  
  49. /* Clear the board */
  50. void Initialize(Board_Type Board) {
  51.     int I;
  52.     for (I = 0; I < Squares; I++)
  53.     Board[I] = Empty;
  54. }
  55.  
  56. /* If a player has won, return the winner. If the game is a tie,
  57.    return 'C' (for cat). If the game is not over, return Empty. */
  58. Square_Type Winner(Board_Type Board) {
  59.     int I;
  60.     for (I = 0; I < Possible_Wins; I++) {
  61.     Square_Type Possible_Winner = Board[Three_in_a_Row[I][0]];
  62.     if (Possible_Winner != Empty &&
  63.         Possible_Winner == Board[Three_in_a_Row[I][1]] &&
  64.         Possible_Winner == Board[Three_in_a_Row[I][2]])
  65.         return Possible_Winner;
  66.     }
  67.  
  68.     for (I = 0; I < Squares; I++)
  69.     if (Board[I] == Empty)
  70.         return Empty;
  71.  
  72.     return 'C';
  73. }
  74.  
  75. /* Return the other player */
  76. Square_Type Other(Square_Type Player) {
  77.     return Player == 'X' ? 'O' : 'X';
  78. }
  79.  
  80. /* Make a move on the board */
  81. void Play(Board_Type Board, int Square, Square_Type Player) {
  82.     Board[Square] = Player;
  83. }
  84.  
  85. /* Print the board */
  86. void Print(Board_Type Board) {
  87.     int I;
  88.     for (I = 0; I < Squares; I += 3) {
  89.     if (I > 0)
  90.         printf("---+---+---\n");
  91.     printf(" %c | %c | %c \n", Board[I], Board[I + 1], Board[I + 2]);
  92.     }
  93.     printf("\n");
  94. }
  95.  
  96. /* Return a heuristic used to determine the order in which the
  97.    children of a node are searched */
  98. int Evaluate(Board_Type Board, Square_Type Player) {
  99.     int I;
  100.     int Heuristic = 0;
  101.     for (I = 0; I < Possible_Wins; I++) {
  102.     int J;
  103.     int Players = 0, Others = 0;
  104.     for (J = 0; J < 3; J++) {
  105.         Square_Type Piece = Board[Three_in_a_Row[I][J]];
  106.         if (Piece == Player)
  107.         Players++;
  108.         else if (Piece == Other(Player))
  109.         Others++;
  110.     }
  111.     Heuristic += Heuristic_Array[Players][Others];
  112.     }
  113.     return Heuristic;
  114. }
  115.  
  116. /* Return the score of the best move found for a board
  117.    The square to move to is returned in *Square */
  118. int Best_Move(Board_Type Board, Square_Type Player, int *Square, int Move_Nbr,
  119.           int Alpha, int Beta) {
  120.     int Best_Square = -1;
  121.     int Moves = 0;
  122.     int I;
  123.     Move_Heuristic_Type Move_Heuristic[Squares];
  124.  
  125.     Total_Nodes++;
  126.  
  127.     /* Find the heuristic for each move and sort moves in descending order */
  128.     for (I = 0; I < Squares; I++) {
  129.     if (Board[I] == Empty) {
  130.         int Heuristic;
  131.         int J;
  132.         Play(Board, I, Player);
  133.         Heuristic = Evaluate(Board, Player);
  134.         Play(Board, I, Empty);
  135.         for (J = Moves-1; J >= 0 &&
  136.                   Move_Heuristic[J].Heuristic < Heuristic; J--) {
  137.         Move_Heuristic[J + 1].Heuristic = Move_Heuristic[J].Heuristic;
  138.         Move_Heuristic[J + 1].Square = Move_Heuristic[J].Square;
  139.         }
  140.         Move_Heuristic[J + 1].Heuristic = Heuristic;
  141.         Move_Heuristic[J + 1].Square = I;
  142.         Moves++;
  143.     }
  144.     }
  145.  
  146.     for (I = 0; I < Moves; I++) {
  147.     int Score;
  148.     int Sq = Move_Heuristic[I].Square;
  149.     Square_Type W;
  150.  
  151.     /* Make a move and get its score */
  152.     Play(Board, Sq, Player);
  153.  
  154.     W = Winner(Board);
  155.     if (W == 'X')
  156.         Score = (Maximum_Moves + 1) - Move_Nbr;
  157.     else if (W == 'O')
  158.         Score = Move_Nbr - (Maximum_Moves + 1);
  159.     else if (W == 'C')
  160.         Score = 0;
  161.     else
  162.         Score = Best_Move(Board, Other(Player), Square, Move_Nbr + 1,
  163.                   Alpha, Beta);
  164.  
  165.     Play(Board, Sq, Empty);
  166.  
  167.     /* Perform alpha-beta pruning */
  168.     if (Player == 'X') {
  169.         if (Score >= Beta) {
  170.         *Square = Sq;
  171.         return Score;
  172.         } else if (Score > Alpha) {
  173.         Alpha = Score;
  174.         Best_Square = Sq;
  175.         }
  176.     } else {
  177.         if (Score <= Alpha) {
  178.         *Square = Sq;
  179.         return Score;
  180.         } else if (Score < Beta) {
  181.         Beta = Score;
  182.         Best_Square = Sq;
  183.         }
  184.     }
  185.     }
  186.     *Square = Best_Square;
  187.     if (Player == 'X')
  188.     return Alpha;
  189.     else
  190.     return Beta;
  191. }
  192.  
  193. /* Provide an English description of the score returned by Best_Move */
  194. void Describe(int Score) {
  195.     if (Score < 0)
  196.     printf("You have a guaranteed win.\n");
  197.     else if (Score == 0)
  198.     printf("I can guarantee a tie.\n");
  199.     else
  200.     printf("I have a guaranteed win by move %d.\n",
  201.            Maximum_Moves - Score + 1);
  202. }
  203.  
  204. /* Have the human or the computer move */
  205. void Move(Board_Type Board, Square_Type Player, int Move_Nbr) {
  206.     int Square;
  207.  
  208.     if (Player == 'X') {
  209.     Total_Nodes = 0;
  210.     Describe(Best_Move(Board, 'X', &Square, Move_Nbr, -Infinity, Infinity));
  211.     printf("%d nodes examined.\n", Total_Nodes);
  212.     Play(Board, Square, 'X');
  213.     printf("Move #%d - X moves to %d\n", Move_Nbr, Square + 1);
  214.     } else {
  215.     do {
  216.         printf("Move #%d - What is O's move? ", Move_Nbr);
  217.         scanf("%d", &Square);
  218.         Square--;
  219.     } while (Board[Square] != ' ');
  220.     Play(Board, Square, 'O');
  221.     }
  222. }
  223.  
  224. /* Play a game of tic-tac-toe */
  225. void Game() {
  226.     Square_Type Player;
  227.     char Answer[String_Length];
  228.     Board_Type Board;
  229.     int Move_Nbr = 1;
  230.  
  231.     Initialize(Board);
  232.  
  233.     printf("\nDo you want to move first? ");
  234.     scanf("%s", Answer);
  235.     if (toupper(Answer[0]) == 'Y')
  236.     Player = 'O';
  237.     else
  238.     Player = 'X';
  239.  
  240.     while(Winner(Board) == ' ') {
  241.     Print(Board);
  242.     Move(Board, Player, Move_Nbr);
  243.     Player = Other(Player);
  244.     Move_Nbr++;
  245.     }
  246.     Print(Board);
  247.  
  248.     if (Winner(Board) != 'C')
  249.     printf("%c wins!\n", Winner(Board));
  250.     else
  251.     printf("It's a tie.\n");
  252. }
  253.  
  254. int main() {
  255.     char Answer[String_Length];
  256.  
  257.     printf("Welcome to Tic-Tac-Toe!\n\n");
  258.     printf("Here is the board numbering:\n");
  259.     printf(" 1 | 2 | 3\n");
  260.     printf("---+---+---\n");
  261.     printf(" 4 | 5 | 6\n");
  262.     printf("---+---+---\n");
  263.     printf(" 7 | 8 | 9\n");
  264.     printf("\n");
  265.     printf("Computer plays X, you play O.\n");
  266.  
  267.     do {
  268.     Game();
  269.     printf("\nDo you want to play again? ");
  270.     scanf("%s", Answer);
  271.     } while (toupper(Answer[0]) == 'Y');
  272. }
  273.  
  274.